package com.gitee.wsl.struct.tree.ext

import com.gitee.wsl.struct.tree.TreeElement
import com.gitee.wsl.struct.tree.TreeNodeException


val <T,E: TreeElement<T, E>> E.path:List<E> get() {
    val that = this
    return buildList {
        var next: E? = that
        while (next != null) {
            add(next)
            next = next.parent
        }
    }.reversed()
}

/**
 * Returns the collection of nodes, which connect the current node with its descendants
 *
 * @param descendant the bottom child node for which the path is calculated
 * @return collection of nodes, which connect the current node with its descendants
 * @throws TreeNodeException exception that may be thrown in case if the current node does not
 *   have such descendant or if the specified tree node is root
 */
@Throws(TreeNodeException::class)
fun <T,E: TreeElement<T, E>> TreeElement<T, E>.path(descendant: TreeElement<T, E>): List<TreeElement<T, E>> {

    val path = mutableListOf<TreeElement<T, E>>()
    var node = descendant
    path.add(node)
    while (!node.isRoot) {
        node = node.parent!!
        path.add(node)
        if (node == this) return path
    }
    throw TreeNodeException(
        "The specified tree node $descendant is not the descendant of tree node $this"
    )
}